package com.leetcode.offer;

/**
 * @author zfl
 * @Classname MaxSlidingWindow
 * @Description 滑动窗口的最大值
 * @Date 2020/11/27 16:50
 */
public class MaxSlidingWindow {

    /**
     * @param nums
     * @param k
     * @return
     * 执行用时：3 ms, 在所有 Java 提交中击败了93.82%的用户
     * 内存消耗：46.4 MB, 在所有 Java 提交中击败了83.31%的用户
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || nums == null) {
            return new int[0];
        }
        int[] num = new int[nums.length - k + 1];
        num[0] = max(nums, 0, k);
        for (int i = 1; i <= nums.length - k; i++) {
            if(num[i - 1] > nums[i - 1]) {
                num[i] = num[i - 1] > nums[i + k - 1] ? num[i - 1] : nums[i + k - 1];
            }else {
                num[i] = max(nums, i, k);
            }
        }
        return num;
    }

    public static int max(int[] nums, int l, int k) {
        int max = nums[l];
        for (int i = l + 1; i < l + k; i++) {
            max = max > nums[i] ? max : nums[i];
        }
        return max;
    }
}
